/**
 * // Definition for a Node.
 * function Node(val,left,right) {
 *    this.val = val;
 *    this.left = left;
 *    this.right = right;
 * };
 */
/**
 * @param {Node} root
 * @return {Node}
 */
 var treeToDoublyList = function(root) {
    if(!root){
        return null;
    }
    let head,node;
    dfs(root);
    head.left=node;
    node.right=head;          // 遍历结束后，head指向头节点，node指向最后的节点
    return head; 
    function dfs(root){
        if(!root){
            return;
        }
        dfs(root.left);
        if(!node){          // 指向中序遍历头节点，中序遍历第一个节点后node才会有值，head指向第一个节点
            head=root;
        }else{               // 中序遍历链接前后两个节点，使得顺序是正确的
            root.left=node;
            node.right=root;
        }
        node=root;            // node 指到下一个节点
        dfs(root.right);
    }
};